package 队列;

import 栈.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class No199二叉树的右视图 {

    /**
     * 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     *
     * 示例:
     *
     * 输入: [1,2,3,null,5,null,4]
     * 输出: [1, 3, 4]
     * 解释:
     *
     *    1            <---
     *  /   \
     * 2     3         <---
     *  \     \
     *   5     4       <---
     */

    /**
     * 1.层序遍历,保存最后一个节点即可
     * 2.或者总是右孩子先行递归遍历,然后当前深度是最深深度,那么将当前节点加入result
     */
    public List<Integer> rightSideView(TreeNode root) {

        if(root==null)
            return new ArrayList<>();

        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        List<Integer> list=new ArrayList<>();

        while (!queue.isEmpty()){
            int count=queue.size();
            while (count>0){
                TreeNode poll = queue.poll();
                if(poll.left!=null)
                    queue.add(poll.left);
                if(poll.right!=null)
                    queue.add(poll.right);
                if(count==1){
                    list.add(poll.val);
                }
                count--;
            }
        }

        return list;
    }

}
